package 二叉搜索树的最小绝对差;

public class Solution {
    /*
    给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
    差值是一个正数，其数值等于两值之差的绝对值。
     */


    int minValue = Integer.MAX_VALUE;
    TreeNode pre = null;

    public int getMinimumDifference(TreeNode root) {
        // 递归
        // 递归参数：根节点，需要使用全局变量记录中序遍历中当前根节点的前一个节点，以及记录当前的最小差值
        // 递归返回值：
        // 递归终止条件：root == null
        // 单层递归逻辑：二叉搜索树的特点就是中序遍历是一个递增序列，所以我们只需要在这个递增序列中找到相邻数字
        // 的最小差值。递归遍历时，不断的继续计算 左子树的值同根节点值的 插值，如果当前插值更小，更新差值即可。
        traversal(root);
        return minValue;
    }

    public void traversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // left
        traversal(root.left);
        // in
        if(pre!=null){
            minValue = Math.min(minValue,root.val-pre.val);
        }
        pre = root;
        // right
        traversal(root.right);
    }
}
